// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-03-01 19:31
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class CopyMaxNumber {
    // 单调栈实现最大数字拼接
    // 单调栈的贪心思想-> 保持栈中的数值大小是按照升序或者降序进行排序->保持栈中的元素尽可能大或者尽可能小
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int[] maxSubSequence = new int[k];
        int start = Math.max(0, k - n);
        int end = Math.min(k, m);
        for (int i = start; i <= end; i++) {
            int[] subsequence1 = maxSubSequences(nums1, i);
            int[] subsequence2 = maxSubSequences(nums2, k - i); // maxSubSequence 用于实现给定几个位置时候获取的最大数字组合
            int[] curMaxSubsequence = merge(subsequence1, subsequence2);// 根据自定义比较器实现对两个数组数据拼接
            if (compare(curMaxSubsequence, 0, maxSubSequence, 0) > 0) { // compare 自定义比较方法
                System.arraycopy(curMaxSubsequence, 0, maxSubSequence, 0, k);
            }
        }
        return maxSubSequence;
    }

    //  按照两个数组的自然顺序合并出最大的数组
    private int[] merge(int[] nums1, int[] nums2) {
        int x = nums1.length;
        int y = nums2.length;
        if (x == 0) {
            return nums2;
        }
        if (y == 0) {
            return nums1;
        }
        int index1 = 0, index2 = 0;
        int k = x + y;
        int[] merge = new int[k];
        for (int i = 0; i < k; i++) {
            if (compare(nums1, index1, nums2, index2) > 0) {
                merge[i] = nums1[index1++];
            } else {
                merge[i] = nums2[index2++];
            }
        }
        return merge;
    }

    // 根据给定的数量和整数数组，获取给定数量大小的字数组
    private int[] maxSubSequences(int[] nums, int k) {
        int n = nums.length;
        int[] stack = new int[k];// 指定数量大小的单调栈，数组的尾部就是栈顶，进行数据的出入
        int remain = n - k; // 当前数组还可以有多少个数字保存->表示当前数组可以排除多少个不要的数字
        int top = -1; // 栈顶指针
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            while (top >= 0 && stack[top] < num && remain > 0) { // top = 0 栈中还有一个元素
                top--;// 新进来的num元素数值比栈顶元素大栈顶元素出栈,直到栈顶元素
                remain--;
            }
            if (top < k - 1) {
                // 当前栈中的元素还没有达到要求
                stack[++top] = num; // 当前符合要求的数字进栈
            } else {
                // 虽然栈中元素已经满了，但是为了达到最大的数字结合，需要遍历整个数组
                remain--; // 当前数字因为太小被淘汰
            }
        }
        return stack;
    }


    // 自定义比较器，比较两个数字字符串中的数字组合大小
    private int compare(int[] nums1, int index1, int[] nums2, int index2) {
        int x = nums1.length;
        int y = nums2.length;
        while (index1 < x && index2 < y) { // 两个数组都还没有遍历到数组结尾
            int different = nums1[index1] - nums2[index2];
            if (different != 0) {
                return different;// nums1 数组小于nums数组
            }
            ++index1;
            ++index2;
        }
        return (x - index1) - (y - index2); // 序号不一定从头开始
    }


    @Test
    public void shout00() {
        int[] nums1 = {3, 4, 6, 5};
        int[] nums2 = {9, 1, 2, 5, 8, 3};
//        int[] nums1 = {3, 4};
//        int[] nums2 = {9, 1, 6};
        int k = 5;
        Arrays.stream(maxNumber(nums1, nums2, k)).forEach(a -> System.out.print(a + "\t"));
    }
}
